package priorityQueue;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueProblem {

    /*
    17.14. 最小K个数
    设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可
    */
    public static int[] smallestK(int[] arr, int k) {
        //k等于0，返回0个元素的数组
        if(k == 0){
            return new int[0];
        }
        //创建一个大堆的优先级队列
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2){
                return o2 - o1;
            }
        });
        //建前k个元素添加到优先队列中
        for(int i = 0; i < k; i++){
            queue.offer(arr[i]);
        }
        //与堆顶元素比较，小于堆顶元素，先将堆顶元素删除，再将小于堆顶的元素插入
        for(int i = k; i < arr.length; i++){
            if(arr[i] < queue.peek()){
                queue.poll();
                queue.offer(arr[i]);
            }
        }
        //创建一个数组，用于储存返回结果
        int[] ret = new int[k];
        for(int i = 0; i < k; i++){
            ret[i] = queue.poll();
        }

        return ret;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{12,5,7,89,10,45,33,66,32,14,22,19,9,36,47};
        int[] ret = smallestK(nums, 5);
        System.out.println(Arrays.toString(ret));
    }
}
